package Greedy;

import java.util.Arrays;

public class K次取反后最大化的数组和 {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int sum = 0;
        boolean zero = false;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num < 0) {
                if (k > 0) {
                    k--;
                    sum -= num;
                } else sum += num;
            } else if (num == 0) zero = true;
            else sum += num;
            min = Math.min(Math.abs(num), min);
        }
        if (zero || k % 2 == 0) return sum;
        else return sum - 2 * min;
    }
}
